home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / lookup.cpp < prev    next >
C/C++ Source or Header  |  1999-05-14  |  42KB  |  1,520 lines
  1. // $Id: lookup.cpp,v 1.5 1999/02/12 14:39:13 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "config.h"
  11. #include <iostream.h>
  12. #include "lookup.h"
  13. #include "symbol.h"
  14. #include "code.h"
  15. #include "ast.h"
  16. #include "case.h"
  17.  
  18. int IntLiteralTable::int32_limit = 0x7FFFFFFF / 10;
  19. LongInt LongLiteralTable::int64_limit = LongInt(0x7FFFFFFF, 0xFFFFFFFF) / 10;
  20.  
  21. int DirectoryTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  22.  
  23. DirectoryTable::DirectoryTable(int estimate) : entry_pool(estimate),
  24.                                                prime_index(0),
  25.                                                hash_size(primes[0])
  26. {
  27.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  28. }
  29.  
  30. DirectoryTable::~DirectoryTable()
  31. {
  32. /*
  33. int n;
  34. int num_slots = 0;
  35. int total = 0;
  36. for (n = 0; n < hash_size; n++)
  37. {
  38. int num = 0;
  39. for (Symbol *s = base[n]; s; s = s -> next)
  40.     num++;
  41. if (num > 0)
  42. {
  43. num_slots++;
  44. total += num;
  45. }
  46. }
  47.  
  48. if (num_slots > 0)
  49. {
  50. cout << "\nDestroying the Name table with " << total
  51.      << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  52. for (n = 0; n < hash_size; n++)
  53. {
  54. int num = 0;
  55. for (Symbol *s = base[n]; s; s = s -> next)
  56.     num++;
  57. if (num > 0)
  58. cout << "    slot " << n << " contains " << num << " element(s)\n";
  59. }
  60. }
  61. if (hash_size < total)
  62.     total = total;
  63. */
  64. #ifdef TEST
  65.     for (int i = 0; i < entry_pool.Length(); i++)
  66.         delete entry_pool[i];
  67.     delete [] base;
  68. #endif
  69. }
  70.  
  71.  
  72. time_t DirectoryEntry::Mtime()
  73. {
  74.     if (mtime_ == 0)
  75.     {
  76.         char *dirname = this -> directory -> DirectoryName();
  77.         int length = this -> directory -> DirectoryNameLength() + this -> length + 1; // +1 for '/'
  78.         char *file_name = new char[length + 1];
  79.         strcpy(file_name, dirname);
  80.         if (dirname[this -> directory -> DirectoryNameLength() - 1] != U_SLASH)
  81.             strcat(file_name, StringConstant::U8S__SL_);
  82.         strcat(file_name, this -> name);
  83.  
  84.         struct stat status;
  85.         if (::SystemStat(file_name, &status) == 0)
  86.             mtime_ = status.st_mtime;
  87. else
  88. assert("Cannot compute system time stamp\n");
  89.  
  90.         delete [] file_name;
  91.     }
  92.  
  93.     return mtime_;
  94. }
  95.  
  96.  
  97. DirectoryEntry *DirectoryTable::FindEntry(char *str, int len)
  98. {
  99.     int k = Hash(str, len) % hash_size;
  100.     DirectoryEntry *entry;
  101.     for (entry = base[k]; entry; entry = entry -> next)
  102.     {
  103.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  104.             return (entry -> IsDummy() ? (DirectoryEntry *) NULL : entry);
  105.     }
  106.  
  107.     return NULL;
  108. }
  109.  
  110.  
  111. void DirectoryTable::Rehash()
  112. {
  113.     hash_size = primes[++prime_index];
  114.  
  115.     delete [] base;
  116.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  117.  
  118.     for (int i = 0; i < entry_pool.Length(); i++)
  119.     {
  120.         DirectoryEntry *e = entry_pool[i];
  121.         int k = Hash(e -> name, e -> length) % hash_size;
  122.         e -> next = base[k];
  123.         base[k] = e;
  124.     }
  125.  
  126.     return;
  127. }
  128.  
  129.  
  130. DirectoryEntry *DirectoryTable::InsertEntry(DirectorySymbol *directory_symbol, char *str, int len)
  131. {
  132.     int k = Hash(str, len) % hash_size;
  133.     DirectoryEntry *entry;
  134.     for (entry = base[k]; entry; entry = entry -> next)
  135.     {
  136.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  137.             return entry;
  138.     }
  139.  
  140.     entry = new DirectoryEntry();
  141.     entry_pool.Next() = entry;
  142.     entry -> Initialize(directory_symbol, str, len);
  143.  
  144.     entry -> next = base[k];
  145.     base[k] = entry;
  146.  
  147.     //
  148.     // If the number of unique elements in the hash table exceeds 2 times
  149.     // the size of the base, and we have not yet reached the maximum
  150.     // allowable size for a base, reallocate a larger base and rehash
  151.     // the elements.
  152.     //
  153.     if ((hash_size < MAX_HASH_SIZE) && (entry_pool.Length() > (hash_size << 1)))
  154.         Rehash();
  155.  
  156.     return entry;
  157. }
  158.  
  159.  
  160. #ifdef WIN32_FILE_SYSTEM
  161. DirectoryEntry *DirectoryTable::FindCaseInsensitiveEntry(char *name, int length)
  162. {
  163.     char *lower_name = new char[length + 1];
  164.     for (int i = 0; i < length; i++)
  165.         lower_name[i] = Case::ToAsciiLower(name[i]);
  166.     lower_name[length] = U_NULL;
  167.  
  168.     DirectoryEntry *entry = FindEntry(lower_name, length);
  169.     delete [] lower_name;
  170.  
  171.     return (entry ? entry -> Image() : entry);
  172. }
  173.  
  174. void DirectoryTable::InsertCaseInsensitiveEntry(DirectoryEntry *image)
  175. {
  176.     int length = image -> length;
  177.     char *lower_name = new char[length + 1];
  178.     for (int i = 0; i < length; i++)
  179.         lower_name[i] = Case::ToAsciiLower(image -> name[i]);
  180.     lower_name[length] = U_NULL;
  181.  
  182.     int k = Hash(lower_name, length) % hash_size;
  183.     DirectoryEntry *entry;
  184.     for (entry = base[k]; entry; entry = entry -> next)
  185.     {
  186.         if (length == entry -> length && memcmp(entry -> name, lower_name, length * sizeof(char)) == 0)
  187.             break;
  188.     }
  189.  
  190.     if (! entry)
  191.     {
  192.         FoldedDirectoryEntry *folded_entry = new FoldedDirectoryEntry(image);
  193.         entry_pool.Next() = folded_entry;
  194.         folded_entry -> Initialize(image, lower_name, length);
  195.  
  196.         folded_entry -> next = base[k];
  197.         base[k] = folded_entry;
  198.  
  199.         //
  200.         // If the number of unique elements in the hash table exceeds 2 times
  201.         // the size of the base, and we have not yet reached the maximum
  202.         // allowable size for a base, reallocate a larger base and rehash
  203.         // the elements.
  204.         //
  205.         if ((hash_size < MAX_HASH_SIZE) && (entry_pool.Length() > (hash_size << 1)))
  206.             Rehash();
  207.     }
  208.  
  209.     delete [] lower_name;
  210.  
  211.     return;
  212. }
  213. #endif
  214.  
  215.  
  216. int NameLookupTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  217.  
  218. NameLookupTable::NameLookupTable(int estimate) : symbol_pool(estimate),
  219.                                                  prime_index(0),
  220.                                                  hash_size(primes[0])
  221. {
  222.     base = (NameSymbol **) memset(new NameSymbol *[hash_size], 0, hash_size * sizeof(NameSymbol *));
  223. }
  224.  
  225. NameLookupTable::~NameLookupTable()
  226. {
  227. /*
  228. int n;
  229. int num_slots = 0;
  230. int total = 0;
  231. for (n = 0; n < hash_size; n++)
  232. {
  233. int num = 0;
  234. for (Symbol *s = base[n]; s; s = s -> next)
  235.     num++;
  236. if (num > 0)
  237. {
  238. num_slots++;
  239. total += num;
  240. }
  241. }
  242.  
  243. if (num_slots > 0)
  244. {
  245. cout << "\nDestroying the Name table with " << total
  246.      << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  247. for (n = 0; n < hash_size; n++)
  248. {
  249. int num = 0;
  250. for (Symbol *s = base[n]; s; s = s -> next)
  251.     num++;
  252. if (num > 0)
  253. cout << "    slot " << n << " contains " << num << " element(s)\n";
  254. }
  255. }
  256. if (hash_size < total)
  257.     total = total;
  258. */
  259. #ifdef TEST
  260.     for (int i = 0; i < symbol_pool.Length(); i++)
  261.         delete symbol_pool[i];
  262.     delete [] base;
  263. #endif
  264. }
  265.  
  266.  
  267. int LiteralLookupTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  268.  
  269. LiteralLookupTable::LiteralLookupTable() : symbol_pool(16384),
  270.                                            prime_index(0),
  271.                                            hash_size(primes[0])
  272. {
  273.     base = (LiteralSymbol **) memset(new LiteralSymbol *[hash_size], 0, hash_size * sizeof(LiteralSymbol *));
  274. }
  275.  
  276. LiteralLookupTable::~LiteralLookupTable()
  277. {
  278. /*
  279. int n;
  280. int num_slots = 0;
  281. int total = 0;
  282. for (n = 0; n < hash_size; n++)
  283. {
  284. int num = 0;
  285. for (Symbol *s = base[n]; s; s = s -> next)
  286.     num++;
  287. if (num > 0)
  288. {
  289. num_slots++;
  290. total += num;
  291. }
  292. }
  293.  
  294. if (num_slots > 0)
  295. {
  296. cout << "\nDestroying the Literal table with " << total
  297.      << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  298. for (n = 0; n < hash_size; n++)
  299. {
  300. int num = 0;
  301. for (Symbol *s = base[n]; s; s = s -> next)
  302.     num++;
  303. if (num > 0)
  304. cout << "    slot " << n << " contains " << num << " element(s)\n";
  305. }
  306. }
  307. if (hash_size < total)
  308.     total = total;
  309. */
  310. #ifdef TEST
  311.     for (int i = 0; i < symbol_pool.Length